LeetCode——全排列II

NO.47 全排列II 中等

思路一：深度遍历，回溯法 本题和前文46.全排列相似，区别在于本题的数组中可能包含重复元素。

根据上一题的经验，已经知道每一条分支路径上每个数组元素只能使用一次，这个问题已经解决了：使用一个nums.length长度的boolean类型的数组标志每个元素的使用情况，false未使用，true已使用。

但是仅仅依靠判断元素的使用情况是不够的，因为数组中可能存在未被使用但是值相等的元素。根据前文40.组合总和II中的经验，相等的元素不能作为兄弟节点，但是可以作为父子节点。于是我们就可以先对nums数组排序，再判断每个节点使用的元素是否和之前一个兄弟节点使用的元素相等，相等则剪枝，语句形如：

1 2	//当前元素和之前一个兄弟节点使用的元素相等，且相等元素节点不是当前节点的父节点 if (i>0 && nums[i]==nums[i-1] && !used[i-1]) continue;

为什么需要” &&!nums[i-1] “，以示例[1,1’,2]来说(只是简单画出了小部分，领会精神即可)：

剪枝的地方没什么问题，但是[ 2,1,1’ ]这个节点使用元素” 1’ “，该节点的索引是1、且等于nums[0]，如果没有” &&!nums[i-1] “的限制也应该被剪枝。但是这个节点应该被保留，是因为相等元素允许作为父子节点，所以” &&!nums[i-1] “的限制是有必要的。

List<List<Integer>> res=new ArrayList<>();
int[] nums;
public List<List<Integer>> permuteUnique(int[] nums) {
    if (nums==null||nums.length==0)return res;
    this.nums=nums;
    //对数组排序，使重复元素紧凑在一起，方便后续剪枝
    Arrays.sort(nums);
    //标记每个元素的使用情况，默认值false表示未使用
    boolean[] flag=new boolean[nums.length];
    dfs(flag,new LinkedList<Integer>());
    return res;
}

private void dfs(boolean[] flag, LinkedList<Integer> track) {
    //完成组合
    if (track.size()==nums.length){
        res.add(new ArrayList<>(new ArrayList<>(track)));
        return;
    }
    for (int i=0;i<nums.length;i++){
        //当前元素未被使用，防止一条路径上出现一个元素被重复使用
        if (!flag[i]){
            //当前元素和之前一个兄弟节点使用的元素相等，且相等元素节点不是当前节点的父节点
            if (i>0&&nums[i]==nums[i-1]&&!flag[i-1])continue;
            //将当前元素加入组合中，并将元素对应的标志置为true
            track.add(nums[i]);
            flag[i]=true;
            dfs(flag,track);
            //每次回溯将最后加入的元素移除，并将被移除元素对应的标志置为false
            track.removeLast();
            flag[i]=false;
        }
    }
}

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github